package bm1;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/7/19 21:37
 * BM1.反转链表
 * https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=295&tqId=23286&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 */
public class Solution {

    // 方法一: 迭代法
    public ListNode ReverseList01(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = pre;
            pre = pre.next;
            cur = curNext;
        }
        return pre;
    }

    // 方法二: 递归法
    public ListNode ReverseList02(ListNode head) {
        // 边界条件
        if (head == null || head.next == null) {
            return head;
        }
        // 递归调用, 反转节点后的链表
        ListNode newHead = ReverseList02(head.next);
        // 将当前节点的下一个节点的 next 指向当前节点, 实现反转
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    // 方法三: 头插法
    public ListNode ReverseList03(ListNode head) {
        // 构造哑巴节点作为头节点
        ListNode muteNode = new ListNode(-1);
        // 逐个向后遍历, 采用头插法的方式构造链表
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next; // 先记录当前节点的后一个节点
            cur.next = muteNode.next;
            muteNode.next = cur;
            cur = curNext;
        }
        return muteNode.next; // 返回头指针
    }

    // 方法四: 利用栈
    public ListNode ReverseList04(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 利用栈遍历一遍链表, 依次存储起来, 而后再依次出栈构造一个反转后的链表并更改 head
        Deque<ListNode> stack = new ArrayDeque<>();
        while (head != null) {
            stack.push(head);
            ListNode headNext = head.next;
            head.next = null;
            head = headNext;
        }
        // 重新构造链表
        head = stack.pop();
        ListNode cur = head;
        while (!stack.isEmpty()) {
            cur.next = stack.pop();
            cur = cur.next;
        }
        return head;
    }


    private static class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }

    // 构造方法
    public Solution() {
        head = null;
    }

    // 创建链表, 便于测试
    public void add(int val) {
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
            return;
        }
        // 找到尾节点, 并添加新节点
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = newNode;
    }

    // 遍历链表, 便于测试
    public void display() {
        if (head == null) {
            System.out.println("当前链表为空");
            return;
        }
        ListNode cur = head;
        while (cur != null) {
            if (cur.next == null) {
                System.out.print(cur.val);
            } else {
                System.out.print(cur.val + "->");
            }
            cur = cur.next;
        }
    }

    private ListNode head;

    public ListNode getHead() {
        return head;
    }

    public void setHead(ListNode head) {
        this.head = head;
    }

    // 测试代码
    public static void main(String[] args) {
        Solution list = new Solution();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.display();
        ListNode newHead = list.ReverseList04(list.getHead());
        list.setHead(newHead);
        // 反转后
        System.out.println("\n反转后链表");
        list.display();
    }
}
